﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ArraysAndStrings.GetRow
{
    class MainProject
    {
        static void Main(string[] args)
        {
            foreach (var item in GetRow(28))
            {
                Console.WriteLine(item);

            }
            Console.ReadKey();
        }
        public static IList<int> GetRow(int rowIndex)
        {
            List<int> list = new List<int>();
            Dictionary<int, int> record = new Dictionary<int, int>();
            //递归
            for (int i = 0; i < rowIndex + 1; i++)
            {
                list.Add(Recursion(rowIndex, i, record));
            }
            return list;
        }

        public static int Recursion(int rowIndex, int i, Dictionary<int,int> dic)
        {
            if (rowIndex == i || i == 0) return 1;
            if (dic.ContainsKey(rowIndex * 1000 + i))
            {
                return dic[rowIndex * 1000 + i];
            }
            int res1 = Recursion(rowIndex - 1, i - 1, dic) ;
            int res2 = Recursion(rowIndex - 1, i, dic);
            if (!dic.ContainsKey(rowIndex  * 1000 + i))
            {
                dic.Add(rowIndex * 1000 + i, res1+ res2);
            }
           
            return res1 + res2;
        }

    }
}
